import java.util.*;
import java.lang.*;

class Node<E>
{
	private E element = null;
	private Node prev = null;
	
	//constructor
	Node(E element, Node post)
	{
		this.element = element;
		
		if (post != null)
		{
			post.prev = this;
		}
		
		this.prev = null;
	}
	
	public boolean hasNext()
	{
		return !(prev == null);
	}
	
	public Node<E> next()
	{
		return this.prev;
	}
	
	public E getElement()
	{
		return element;
	}
	
}

interface LinkedStackInterface<E> extends Iterable<E> {

    public boolean empty( );
    public int size( );
    public void clear( );
    public E top( );
    public E pop( ) throws EmptyStackException;
    public void push(E elem);
    public java.util.Iterator<E> iterator( );

}


public class LinkedStack<E> implements LinkedStackInterface<E>
{
	private Node<E> top = null;
	private Node<E> bottom = null;
	
	private int size = 0;
	
	LinkedStack()
	{
		bottom = new Node<E>(null, null);
		top = bottom;
		
		size = 0;
	}
	
    public boolean empty()
    {
    	return size == 0;
    }
    
    public int size()
    {
    	return size;
    }
    
    public void clear( )
    {
    	size = 0;
    	top = bottom;
    }
    
    public E top() throws EmptyStackException
    {
    	if (size == 0)
    	{
    		throw new EmptyStackException();
    	}
    	
    	return top.getElement();
    }
    
    public E pop() throws EmptyStackException
    {
    	if (size == 0)
    	{
    		throw new EmptyStackException();
    	}
    	
    	size--;
    	
    	Node tmp = top;
    	
    	Node topPost = bottom;
    	while(topPost.next() != top)
    	{
    		topPost = topPost.next();
    	}
    	
    	top = topPost;
    	
    	return (E)tmp.getElement();
    }
    
    public void push(E elem)
    {
    	Node<E> tmp = new Node<E>(elem, top);
    		
    	size++;
    	
    	//System.out.println(elem);
    	
    	top = tmp;
    }
    
    class LinkedStackIterator<E> implements java.util.Iterator<E>
    {
    	private Node<E> top = null;
    	private Node<E> bottom = null;
    	
    	private int size = 0;
    	
    	private boolean calledBefore = false;
    	
    	LinkedStackIterator(LinkedStack stack)
    	{
    		top = stack.top;
    		bottom = stack.bottom.next();
    		
    		size = stack.size;
    	}
    	
    	public boolean hasNext()
    	{
    		return !(size == 0);
    	}
    	
    	public E next() throws NoSuchElementException
    	{
    		calledBefore = true;
    		
    		if (size == 0)
    		{
    			throw new NoSuchElementException();
    		}
    		
    		return bottom.getElement();
    	}
    	
    	public void remove() throws IllegalStateException
    	{
    		if (calledBefore == false)
    		{
    			throw new IllegalStateException();
    		}
    		
    		calledBefore = false;
    		
    		size--;

    		bottom = bottom.next();
    	}

    }
    
    public java.util.Iterator<E> iterator( )
    {
    	return new LinkedStackIterator<E>(this);
    }
    
    public static void main(String args[])
    {
    	LinkedStack<Integer> stack = new LinkedStack<Integer>();
    	
    	stack.push(1);
    	stack.push(2);
    	stack.push(3);
    	
    	System.out.println(stack.pop());
    	System.out.println(stack.size());
    	System.out.println(stack.empty());
    	System.out.println(stack.pop());
    	System.out.println(stack.pop());
    	System.out.println(stack.size());
    	System.out.println(stack.empty());
    	System.out.println(stack.pop());
    }
}
